//
// Created by Hello on 2024/2/3.
//
#include <stdio.h>
#include <string.h>
// 20. 有效的括号
// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

#define true 1
#define false 0
typedef int bool;

#define MaxSize 4000
// 栈的定义及其基本运算算法
typedef struct {
    char data[MaxSize]; // 存放栈中的数据元素
    int top;
} SqStack;
// 初始化栈
void InitStack(SqStack *st)
{
    st->top = -1;   // 栈顶指针置为-1
}
// 判断栈是否为空
bool StackEmpty(SqStack *st) {
    return st->top == -1;
}
// 进栈
bool Push(SqStack *st, char e)
{
    if(st->top == MaxSize-1)    // 栈满
        return false;
    st->top++;
    st->data[st->top] = e;
    return true;
}
// 出栈
char Pop(SqStack *st)
{
    char e = st->data[st->top]; // 取出栈顶元素
    st->top--;  // 栈顶指针减1
    return e;
}
// 取栈顶元素
char GetTop(SqStack *st)
{
    return st->data[st->top];
}

bool isValid(char* s) {
    SqStack st; // 定义一个顺序栈
    InitStack(&st); // 初始化st
    size_t n = strlen(s);  // 求字符串长度n

    for(int i = 0; i < n; i++)
    {
        if(s[i] == '(' || s[i] == '[' || s[i] == '{')
            Push(&st, s[i]);    // 所有左括号进栈
        else {
            if(StackEmpty(&st)) // 栈空时返回false
                return false;

            char e = GetTop(&st);   // 取栈顶元素
            if(s[i] == ')')
            {
                if(e != '(')    // 不配对
                    return false;
                else
                    Pop(&st);   // 出栈，继续匹配
            }
            else if(s[i] == ']')
            {
                if(e != '[')
                    return false;
                else
                    Pop(&st);
            }
            else if(s[i] == '}')
            {
                if(e != '{')
                    return false;
                else
                    Pop(&st);
            }
        }
    }
    if(!StackEmpty(&st)) return false;  // 栈不空返回false
    return true;
}
int main()
{
    printf("%d\n", isValid("()"));
    printf("%d\n", isValid("()[]{}"));
    printf("%d\n", isValid("(]"));
}